package com.tushen.datacenter.ts.data;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class Test {


    //0代表还没填数字
    private static int[] ARRAY0 = {7,0,0,0,5,0,0,0,1};
    private static int[] ARRAY1 = {8,0,0,0,0,0,0,0,6};
    private static int[] ARRAY2 = {0,0,0,3,0,0,4,2,0};

    private static int[] ARRAY3 = {8,0,0,0,0,0,0,0,4};
    private static int[] ARRAY4 = {0,0,2,0,8,0,3,0,0};
    private static int[] ARRAY5 = {6,0,0,0,0,0,0,0,5};

    private static int[] ARRAY6 = {0,6,8,0,0,9,0,0,0};
    private static int[] ARRAY7 = {9,0,0,0,0,0,0,0,4};
    private static int[] ARRAY8 = {2,0,0,0,4,0,0,0,7};

    private static int[] EMPTY_POS0 = {1,2,3,5,6,7};
    private static int[] EMPTY_POS1 = {1,2,3,4,5,6,7};
    private static int[] EMPTY_POS2 = {0,1,2,4,5,8};

    private static int[] EMPTY_POS3 = {1,2,3,4,5,6,7};
    private static int[] EMPTY_POS4 = {0,1,3,5,7,8};
    private static int[] EMPTY_POS5 = {1,2,3,4,5,6,7};

    private static int[] EMPTY_POS6 = {0,3,4,6,7,8};
    private static int[] EMPTY_POS7 = {1,2,3,4,5,6,7};
    private static int[] EMPTY_POS8 = {1,2,3,5,6,7};

    private static  int[] MARGIN0 = {2,3,4,6,8,9};
    private static  int[] MARGIN1 = {1,2,3,4,5,7,9};
    private static  int[] MARGIN2 = {1,5,6,7,8,9};

    private static  int[] MARGIN3 = {1,2,3,5,6,7,9};
    private static  int[] MARGIN4 = {1,4,5,6,7,9};
    private static  int[] MARGIN5 = {1,2,3,4,7,8,9};

    private static  int[] MARGIN6 = {1,2,3,4,5,7};
    private static  int[] MARGIN7 = {1,2,3,5,6,7,8};
    private static  int[] MARGIN8 = {1,3,5,6,8,9};

    private static List<List<Integer>> permuteResult0 = new ArrayList<>();
    private static List<List<Integer>> permuteResult1 = new ArrayList<>();
    private static List<List<Integer>> permuteResult2 = new ArrayList<>();
    private static List<List<Integer>> permuteResult3 = new ArrayList<>();
    private static List<List<Integer>> permuteResult4 = new ArrayList<>();
    private static List<List<Integer>> permuteResult5 = new ArrayList<>();
    private static List<List<Integer>> permuteResult6 = new ArrayList<>();
    private static List<List<Integer>> permuteResult7 = new ArrayList<>();
    private static List<List<Integer>> permuteResult8 = new ArrayList<>();

    public static boolean isValidSudoku(char[][] board) {

        for (int i=0;i<9;i++) {
            int[] cols = new int[9];
            int[] rows = new int[9];
            int[] blocks = new int[9];
            for (int j=0;j<9;j++) {
                // 遍历行，-‘1’是为了用0-8索引存下1-9

                if (board[i][j] == '.') {

                }
                else if (rows[board[i][j]-'1']==1){
                    return false;
                }
                else{
                    rows[board[i][j]-'1']=1;
                }

                // 遍历列
                if (board[j][i] == '.') {

                }
                else if (cols[board[j][i]-'1']==1){
                    return false;
                }
                else{
                    cols[board[j][i]-'1']=1;
                }
                // 遍历块，将ij坐标系转换到正方形坐标系，理解不了可以背
                int m = i/3*3 + j/3;
                int n = i%3*3 + j%3;

                if (board[m][n]== '.') {

                }
                else if (blocks[board[m][n]-'1']==1) {
                    return false;
                }
                else {
                    blocks[board[m][n]-'1']=1;
                }
            }
        }
        return true;
    }


    public static  void main(String[] args){


        permute(MARGIN0,0,MARGIN0.length-1,0);
        permute(MARGIN1,0,MARGIN1.length-1,1);
        permute(MARGIN2,0,MARGIN2.length-1,2);
        permute(MARGIN3,0,MARGIN3.length-1,3);
        permute(MARGIN4,0,MARGIN4.length-1,4);
        permute(MARGIN5,0,MARGIN5.length-1,5);
        permute(MARGIN6,0,MARGIN6.length-1,6);
        permute(MARGIN7,0,MARGIN7.length-1,7);
        permute(MARGIN8,0,MARGIN8.length-1,8);


        for(int i=0;i< permuteResult0.size();i++){
            for(int i1=0;i1< permuteResult1.size();i1++){
                for(int i2=0;i2< permuteResult2.size();i2++){
                    for(int i3=0;i3< permuteResult3.size();i3++){
                        for(int i4=0;i4< permuteResult4.size();i4++){
                            for(int i5=0;i5< permuteResult5.size();i5++){
                                for(int i6=0;i6< permuteResult6.size();i6++){
                                    for(int i7=0;i7< permuteResult7.size();i7++){
                                        for(int i8=0;i8< permuteResult8.size();i8++){

                                            if(check(permuteResult0.get(i),permuteResult1.get(i1),permuteResult2.get(i2),
                                                    permuteResult3.get(i3),permuteResult4.get(i4),permuteResult5.get(i5),
                                                    permuteResult6.get(i6),permuteResult7.get(i7),permuteResult8.get(i8))){
                                                return;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    private static int[] combine(int[] arr,int[] empty,List<Integer> list){

        int[] newArr = new int[9];

        for(int i=0;i< arr.length;i++){
            if(arr[i] != 0){
                newArr[i] = arr[i];
            }
        }
        int k= 0;
        for(int a:empty){
            newArr[a] = list.get(k);
            k++;
        }
        return newArr;
    }

    private static  boolean checkH(int[] a1,int[] a2,int[] a3){

        int[] checkArr = new int[9];
        for(int i= 1;i< 9;i++){
            checkArr[i] = 0;
        }
        checkArr[a1[0]] = a1[0];
        checkArr[a1[1]] = a1[1];
        checkArr[a1[2]] = a1[2];
        checkArr[a2[0]] = a2[0];
        checkArr[a2[1]] = a2[1];
        checkArr[a2[2]] = a2[2];
        checkArr[a3[0]] = a3[0];
        checkArr[a3[1]] = a3[1];
        checkArr[a3[2]] = a3[2];
        for(int i= 1;i< 9;i++){
            if(checkArr[i] == 0){
                return false;
            }
        }

        for(int i= 1;i< 9;i++){
            checkArr[i] = 0;
        }
        checkArr[a1[3]] = a1[3];
        checkArr[a1[4]] = a1[4];
        checkArr[a1[5]] = a1[5];
        checkArr[a2[3]] = a2[3];
        checkArr[a2[4]] = a2[4];
        checkArr[a2[5]] = a2[5];
        checkArr[a3[3]] = a3[3];
        checkArr[a3[4]] = a3[4];
        checkArr[a3[5]] = a3[5];
        for(int i= 1;i< 9;i++){
            if(checkArr[i] == 0){
                return false;
            }
        }

        for(int i= 1;i< 9;i++){
            checkArr[i] = 0;
        }
        checkArr[a1[6]] = a1[6];
        checkArr[a1[7]] = a1[7];
        checkArr[a1[8]] = a1[8];
        checkArr[a2[6]] = a2[6];
        checkArr[a2[7]] = a2[7];
        checkArr[a2[8]] = a2[8];
        checkArr[a3[6]] = a3[6];
        checkArr[a3[7]] = a3[7];
        checkArr[a3[8]] = a3[8];
        for(int i= 1;i< 9;i++){
            if(checkArr[i] == 0){
                return false;
            }
        }

        return true;
    }

    private static  boolean checkV(int[] a1,int[] a2,int[] a3){

        int[] checkArr = new int[9];
        for(int i= 1;i< 9;i++){
            checkArr[i] = 0;
        }
        checkArr[a1[0]] = a1[0];
        checkArr[a1[3]] = a1[3];
        checkArr[a1[6]] = a1[6];
        checkArr[a2[0]] = a2[0];
        checkArr[a2[3]] = a2[3];
        checkArr[a2[6]] = a2[6];
        checkArr[a3[0]] = a3[0];
        checkArr[a3[3]] = a3[3];
        checkArr[a3[6]] = a3[6];
        for(int i= 1;i< 9;i++){
            if(checkArr[i] == 0){
                return false;
            }
        }

        for(int i= 1;i< 9;i++){
            checkArr[i] = 0;
        }
        checkArr[a1[1]] = a1[1];
        checkArr[a1[4]] = a1[4];
        checkArr[a1[5]] = a1[7];
        checkArr[a2[1]] = a2[1];
        checkArr[a2[4]] = a2[4];
        checkArr[a2[7]] = a2[7];
        checkArr[a3[1]] = a3[1];
        checkArr[a3[4]] = a3[4];
        checkArr[a3[7]] = a3[7];
        for(int i= 1;i< 9;i++){
            if(checkArr[i] == 0){
                return false;
            }
        }

        for(int i= 1;i< 9;i++){
            checkArr[i] = 0;
        }
        checkArr[a1[2]] = a1[2];
        checkArr[a1[5]] = a1[5];
        checkArr[a1[8]] = a1[8];
        checkArr[a2[2]] = a2[2];
        checkArr[a2[5]] = a2[5];
        checkArr[a2[8]] = a2[8];
        checkArr[a3[2]] = a3[2];
        checkArr[a3[5]] = a3[5];
        checkArr[a3[8]] = a3[8];
        for(int i= 1;i< 9;i++){
            if(checkArr[i] == 0){
                return false;
            }
        }

        return true;
    }

    private static  boolean checkX1(int[] a1,int[] a2,int[] a3) {

        int[] checkArr = new int[9];
        for (int i = 1; i < 9; i++) {
            checkArr[i] = 0;
        }
        checkArr[a1[0]] = a1[0];
        checkArr[a1[4]] = a1[4];
        checkArr[a1[8]] = a1[8];
        checkArr[a2[0]] = a2[0];
        checkArr[a2[4]] = a2[4];
        checkArr[a2[8]] = a2[8];
        checkArr[a3[0]] = a3[0];
        checkArr[a3[4]] = a3[4];
        checkArr[a3[8]] = a3[8];
        for (int i = 1; i < 9; i++) {
            if (checkArr[i] == 0) {
                return false;
            }
        }

        return true;
    }

    private static  boolean checkX2(int[] a1,int[] a2,int[] a3) {

        int[] checkArr = new int[9];
        for (int i = 1; i < 9; i++) {
            checkArr[i] = 0;
        }
        checkArr[a1[2]] = a1[2];
        checkArr[a1[4]] = a1[4];
        checkArr[a1[6]] = a1[6];
        checkArr[a2[2]] = a2[2];
        checkArr[a2[4]] = a2[4];
        checkArr[a2[6]] = a2[6];
        checkArr[a3[2]] = a3[2];
        checkArr[a3[4]] = a3[4];
        checkArr[a3[6]] = a3[6];
        for (int i = 1; i < 9; i++) {
            if (checkArr[i] == 0) {
                return false;
            }
        }

        return true;
    }
    private static  boolean check(List<Integer> l1,List<Integer> l2,List<Integer> l3,
                                  List<Integer> l4,List<Integer> l5,List<Integer> l6,
                                  List<Integer> l7,List<Integer> l8,List<Integer> l9){

        int[] arr0 = combine(ARRAY0,EMPTY_POS0,l1);
        int[] arr1 = combine(ARRAY1,EMPTY_POS1,l2);
        int[] arr2 = combine(ARRAY2,EMPTY_POS2,l3);
        int[] arr3 = combine(ARRAY3,EMPTY_POS3,l4);
        int[] arr4 = combine(ARRAY4,EMPTY_POS4,l5);
        int[] arr5 = combine(ARRAY5,EMPTY_POS5,l6);
        int[] arr6 = combine(ARRAY6,EMPTY_POS6,l7);
        int[] arr7 = combine(ARRAY7,EMPTY_POS7,l8);
        int[] arr8 = combine(ARRAY8,EMPTY_POS8,l9);
        if(!checkH(arr0,arr1,arr2)){
            return false;
        }
        if(!checkH(arr3,arr4,arr5)){
            return false;
        }
        if(!checkH(arr6,arr7,arr8)){
            return false;
        }

        if(!checkV(arr0,arr3,arr6)){
            return false;
        }
        if(!checkV(arr1,arr4,arr7)){
            return false;
        }

        if(!checkV(arr2,arr5,arr8)){
            return false;
        }

        return true;

    }


    private static  List<Integer> arrayToList(int array[]){
        List<Integer> list = new ArrayList<>();

        for(int a:array){
            list.add(a);
        }
        return list;

    }
    private  static void storePermute(int array[],int i){

        if(i == 0){
            permuteResult0.add(arrayToList(array));
        }else if(i == 1){
            permuteResult1.add(arrayToList(array));
        }else if(i == 2){
            permuteResult2.add(arrayToList(array));
        }else if(i == 3){
            permuteResult3.add(arrayToList(array));
        }else if(i == 4){
            permuteResult4.add(arrayToList(array));
        }else if(i == 5){
            permuteResult5.add(arrayToList(array));
        }else if(i == 6){
            permuteResult6.add(arrayToList(array));
        }else if(i == 7){
            permuteResult7.add(arrayToList(array));
        }else if(i == 8){
            permuteResult8.add(arrayToList(array));
        }


    }

    private static void printA(){

        System.out.print(ARRAY0[0]+" "+ARRAY0[1]+" "+ARRAY0[2]+" "+ARRAY1[0]+" "+ARRAY1[1]+" "+ARRAY1[2]+" "+ARRAY2[0]+" "+ARRAY2[1]+" "+ARRAY2[2]+" ");
        System.out.println();
        System.out.print(ARRAY0[3]+" "+ARRAY0[4]+" "+ARRAY0[5]+" "+ARRAY1[3]+" "+ARRAY1[4]+" "+ARRAY1[5]+" "+ARRAY2[3]+" "+ARRAY2[4]+" "+ARRAY2[5]+" ");
        System.out.println();
        System.out.print(ARRAY0[6]+" "+ARRAY0[7]+" "+ARRAY0[8]+" "+ARRAY1[6]+" "+ARRAY1[7]+" "+ARRAY1[8]+" "+ARRAY2[6]+" "+ARRAY2[7]+" "+ARRAY2[8]+" ");
        System.out.println();

        System.out.print(ARRAY3[0]+" "+ARRAY3[1]+" "+ARRAY3[2]+" "+ARRAY4[0]+" "+ARRAY4[1]+" "+ARRAY4[2]+" "+ARRAY5[0]+" "+ARRAY5[1]+" "+ARRAY5[2]+" ");
        System.out.println();
        System.out.print(ARRAY3[3]+" "+ARRAY3[4]+" "+ARRAY3[5]+" "+ARRAY4[3]+" "+ARRAY4[4]+" "+ARRAY4[5]+" "+ARRAY5[3]+" "+ARRAY5[4]+" "+ARRAY5[5]+" ");
        System.out.println();
        System.out.print(ARRAY3[6]+" "+ARRAY3[7]+" "+ARRAY3[8]+" "+ARRAY4[6]+" "+ARRAY4[7]+" "+ARRAY4[8]+" "+ARRAY5[6]+" "+ARRAY5[7]+" "+ARRAY5[8]+" ");
        System.out.println();

        System.out.print(ARRAY6[0]+" "+ARRAY6[1]+" "+ARRAY6[2]+" "+ARRAY7[0]+" "+ARRAY7[1]+" "+ARRAY7[2]+" "+ARRAY8[0]+" "+ARRAY8[1]+" "+ARRAY8[2]+" ");
        System.out.println();
        System.out.print(ARRAY6[3]+" "+ARRAY6[4]+" "+ARRAY6[5]+" "+ARRAY7[3]+" "+ARRAY7[4]+" "+ARRAY7[5]+" "+ARRAY8[3]+" "+ARRAY8[4]+" "+ARRAY8[5]+" ");
        System.out.println();
        System.out.print(ARRAY6[6]+" "+ARRAY6[7]+" "+ARRAY6[8]+" "+ARRAY7[6]+" "+ARRAY7[7]+" "+ARRAY7[8]+" "+ARRAY8[6]+" "+ARRAY8[7]+" "+ARRAY8[8]+" ");
        System.out.println();

        System.out.println("==================================");
    }


    private static void permute(int array[], int begin, int end,int seq)
    {
        if (begin == end)
        {
            storePermute(array,seq);
        }
        else
        {
            for (int j = begin; j <= end; ++j)
            {
                swap(array,j,begin);
                permute(array, begin+1, end,seq); //recursive，enlarge problem's scope
                swap(array,j, begin); //backtracking
            }
        }
    }



    private static void  swap(int[] arr,int a, int b)
    {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

}
